In recent issues, we've discussed how container and iterator classes can simplify your C++ programs. Initially, we looked at creating iterator classes you could use with C-style arrays or your own containers ("An Introduction to Iterator Classes," July 1994).
Later, we compared this approach with that of using the container classes and iterator classes that are part of Borland's object-based container class library ("More on Iterator Classes," August 1994). Finally, we examined the Borland International Data Structures (BIDS) container and iterator classes and demonstrated the programming style they encourage ("Using the BIDS Iterator Classes," December 1994).
Unfortunately, each C++ compiler vendor seems to have created different, and often incompatible, designs for the container class libraries they ship. Since containers and iterators are common elements of non-trivial C++ programs, it was inevitable that the C++ programming community would search for a common solution that all C++ programmers could use.
As a result, the American National Standards Institute and International Standards Organization (ANSI/ISO) C++ committee decided to include the Standard Template Library (STL) as part of the forthcoming C++ standard. The STL, created by Alex Stepanov and Meng Lee of Hewlett-Packard, is a framework of template classes and template functions that provide most, if not all, of the container and iterator data structures you're likely to need for C++ programs.
In this article, we'll compare STL containers and iterators
to BIDS containers and iterators you may have already used. To
demonstrate how you can use STL classes and functions instead
of the BIDS components, we'll rewrite the example program
from the December issue using STL containers and iterators.
First, let's briefly review the BIDS library. As you probably
know, the BIDS library defines three concrete types of
containers (types you'll use directly): collections, associations,
and sequences. Typically, underneath these concrete BIDS classes
are implementation classes, on which Borland bases concrete
classes.
To see how the implementation classes in the BIDS library relate to the concrete classes, consider the TArrayAsVector<> and TDVectorImp<> template classes. Figure A shows the relationships between the TArrayAsVector<> template class and its base classes, the relationship between the TDVectorImp<> template class and its bases, and the relationship of these two hierarchies to each other.
Figure A - The concrete classes and the implementation classes have a complex relationship.
Fortunately, you don't need to specify the interactions
between these classesBorland has already defined the
interactions and created several concrete classes for you. The
implementation classes that the BIDS library uses represent the
basic data structures that programmers have been using for years:
The BIDS concrete classes build on the data structures that we
just identified to provide different interfaces to the same low-level
implementation.
A BIDS Collection is basically an unordered set of objects. The
two types of collections are Bag and Set. The only difference
between a Bag and a Set is that a Set doesn't allow you
to store multiple objects of the same value.
A BIDS Association is a set of paired elements. The two types
of associations are Association and Dictionary. The Association
class defines a relationship between a key element and a value
element. The Dictionary class represents a set of associations.
A BIDS Sequence is an ordered, dynamically sized set of objects
you can access in very specific ways. The four Sequences are Queue,
Deque, Stack, and Array. The Queue, Deque, and Stack classes restrict
your access to one (or two, in the case of the Deque) element
in the Set at a time. The Array class allows you to access any
element in the Set via an integral index value.
In comparison to the BIDS library, the STL seems somewhat sparse and simple. This is true for a couple of reasons. First, the BIDS classes contain a large number of intermediate classes to enhance flexibility, allowing you to combine the classes in several ways.
Second, the STL puts container manipulation code in global template
functions that Borland included as member functions of specific
BIDS classes. Later we'll compare these approaches.
An STL collection is an ordered container of objects. (This is
in contrast to the collection classes in the BIDS library, where
collections are unordered.) In the STL, you'll find two
collectionsSet and Multiset. The Set class specifies
an ordered collection for unique objects. The Multiset class allows
duplicate objects and, therefore, corresponds roughly to the Bag
class from the BIDS library.
In the BIDS library, you had to create an instance of the Association
class (using a Key object and a Value object) before you could
create a Dictionary of those associations. The STL bypasses this
intermediate step by causing the Association classes to create
instances of the Pair class (a utility class that defines paired
values of possibly different types). The two association classes
are Map and Multimap. The Map class corresponds directly to the
BIDS Dictionary classit stores a collection of Pair objects
and allows you to retrieve the value component of the Pair object
based on a given key. The Multimap class provides this same behavior,
but it allows duplicate keys for its Pair objects.
As with the BIDS classes, STL sequence classes define ordered collections of objects you can access in specific ways. The three sequence classes are Vector, Deque, and List. You'll notice that the STL doesn't provide a separate implementation class for vectors and lists as the BIDS library does. Instead, it provides a more comprehensive interface that's used as a concrete class. As with their BIDS counterparts, an STL Vector allows you to access any element via an integral index, and an STL Deque allows you to add elements to or remove them from either end.
In addition, the STL provides a List class as a concrete class.
The List class allows you to add elements to or remove them from
the middle of the sequence more quickly than you could from a
Vector or a Deque, but you have to traverse the list to access
a specific element.
If you begin using the adaptor classes, the BIDS library and STL start to look very similar. In the STL, the Adaptor classes allow you to limit the functions that are accessible.
Specifically, the Adaptor classes allow you to modify the way
the Sequence classes store or retrieve their elements. The three
Adaptor classes are Stack, Queue, and Priority Queue. To implement
a Stack, you can use any of the Sequence classes to provide the
storagethe Stack class simply translates "stack
functions" into function calls that are appropriate for
one of the Sequence classes. The Stack class merely provides a
pop( ) member function that calls
c.pop_back( );
where c is an identifier for the adaptor's implementation
sequence.
To get a better idea of how you can use the STL classes in place of the BIDS classes, let's rewrite the example program from the December article. Before you start, you'll want to create a new directory for the STL header files and copy them into that directory. (If you don't already have the STL files, see How to get the STL, for information on acquiring the STL and its accompanying documentation.
To create the new directory, enter the following at a DOS command
line:
md \BC4\INCLUDE\STL
Then, perform a simple DOS file copy to transfer all STL header files to that directory.
To create our example program, launch the Borland C++ 4.0 Integrated Development Environment (IDE). When the IDE's main window appears, choose New from the File menu and enter the program that appears in Listing A.
Listing A: STL_TEST.CPP
#include "\bc4\include\stl\vector.h"
#include "\bc4\include\stl\list.h"
#include "\bc4\include\stl\deque.h"
#include <iostream.h>
typedef vector<float> Group;
typedef Group::iterator Iterator;
int main( )
{
// Create a container
Group numbers;
float num = 1.01;
for(int count = 1;
count < 6;
++count)
{
num = num * count;
numbers.push_back(num);
cout << num << endl;
}
cout << endl; // Add space
while(!numbers.empty( ))
{
cout << numbers.back( ) << endl;
numbers.pop_back( );
}
return 0;
}
When you finish entering the code, choose Save from the File menu and enter STL_TEST.CPP in the Save File As entry field. Click OK to save the file.
Next, right-click on the window for the code you just entered and choose Target Expert... from the pop-up menu. When the TargetExpert dialog box appears, choose EasyWin from the Target Type list box. Click OK when you're finished.
To make the STL files accessible, choose Project... from the Options menu. In the Project Options dialog box, click on Directories in the Topics list, and then add the path \BC4\INCLUDE\STL to the STL files at the end of the Include Source Directory entry field. Click OK to save this change.
Before you build any programs that use the STL, you'll need to make some minor changes for Borland C++ compatibility. (See Modifying the STL to work with Borland C++ 4.x, for more information.)
Now, choose Run from the Debug menu to build and run the program.
When the program runs, you'll see the following output:
1.01 2.02 6.06 24.24 121.2
121.2 24.24 6.06 2.02 1.01
After you've confirmed that the output from the program is correct, double-click on the output window to close it.
If you examine this new version of the program, you'll
notice several details of the STL itself. For example, instead
of declaring an iterator type with another template, you'll
notice that the STL defines the iterator (Group::iterator)
as a nested type of the container class. Also, the push_back( ),
empty( ), back( ), and pop_back( )
member functions demonstrate some of the STL container classes'
common interface.
As you may have noticed, we designed STL_TEST to use iterators
differently from how they were used in the December article. We
did this so we could present the STL iterators separately.
In the BIDS library, most of the container classes have their own iterator classes. For example, to iterate a TArrayAsVector<> or BI_ArrayAsVector<> array, you'd use either a TArrayAsVectorIterator<> object or a BI_ArrayAsVectorIterator<> object.
Because the BIDS library contains an iterator template class for
most of the container template classes, the library is quite large.
Fortunately, Borland defined a fairly consistent interface in
each of the iterator classes, which made it easy to use, despite
its size. (We demonstrated this in the December article by changing
the underlying storage from a Stack container to a Queue container.
The iterator interface is the same for both container types.)
Similarly, the STL defines several types of iterator classes that have a very consistent interface within each type. The iterator types are: input, output, forward, bidirectional, and random access.
For example, each of the three sequence classes uses a specific
type of iterator object. Table A lists the sequence classes and
their corresponding iterator types.
Table A: Sequence classes and their iterators
| Sequence class | Iterator |
| Vector | random access |
| Deque | random access with distance specifier |
| List | bidirectional |
The random access iterator the Vector class uses is the simplest typea pointer to an object in the vector. This makes the Vector class an ideal component for wrapping around simple C++ arrays, because a pointer to any element in an array is a valid iterator for that type. (Since the Vector class uses simple, but managed, C++ arrays for its low-level storage, this makes perfect sense.)
The result of this design is that you can use pointers to array
elements even if the array isn't wrapped inside the
STL Vector class. For example, if you create an array of char
values using
char str[20];
you can use str, &(str[0]), or &(str[5])
as random access iterators. This means you can call the find( )
template function by writing
find(str, &(str[20]), "t");
and the template function will correctly return a pointer to a
"t" that appears in that array.
While the Vector class uses simple pointers as random access iterators,
the Deque class requires something to differentiate its iterators.
This differentiation is necessary because elements may not have
the same conceptual position in the deque that they have in memory.
Because of the possible differences in conceptual position, moving
"up" from a given position in the deque may cause
the iterator to wrap around to the beginning of the deque's
storage.
Unlike the random access iterators that the Vector and Deque classes
use, the List class's iterators can move to another position
only by "walking" the list (moving one list element
at a time). This is because any given list element has access
only to the elements immediately ahead of and behind it. This
limitation makes it impossible to define a reasonable random access
method for a List object.
When you're trying to understand what the STL iterator classes represent, it may be easier to think of these types of iterators in terms of their behavior, instead of considering them related classes (which they aren't). What each type of iterator shares with other iterators of the same type is the interface it provides.
When you think of iterators this way, the different type categories become a set of operations that an iterator must provide. These rules are enforced by the different function templates the STL supplies.
For example, the sort( ) template function expects a random access iterator, which defines the common mathematical relationshipsoperator-( ), operator+( ), operator==( ), and so on. If you try to call the sort( ) function using iterators from a List, the compiler will generate Illegal Structure Operation errors for the lines of code that try to perform math operations on iterators that define only the pre-increment and pre-decrement operators.
However, since the random access iterators you can use with a
Vector object provide the same operations that the Deque class's
iterators provide, you can use the sort( ) function
with iterators from either type of container. This is analogous
to the global displayMatches( ) function that we
used in the December article.
Now, let's rewrite the displayMatches( )
function. As you may recall from the December article, this function
had a very simple purpose: Search the container for values between
1 and 3 and display them via the standard output stream, cout.
For reference, this function appears in Figure B.
Figure B - You need to change the displayMatches( ) function to make it compatible with the STL.
void
displayMatches(Iterator &i)
{
i.restart( );
while(i)
{
float temp = i.current( );
if((temp > 1) && (temp < 3))
{
cout << "Item " << i.current( );
cout << " is between 1 and 3" << endl;
}
++i;
}
}
To write the displayMatches( ) function as an STL-compatible function, you need to make two changes. First, you must change the function's argument list to accept a second iterator that represents the last item in the container.
The BIDS iterator classes all provide an operator int( ) conversion operator that returns 0 if the iterator no longer points to a valid element in its container. Unfortunately, this design prevents us from using low-level constructs like simple pointers as iterators.
Instead, the STL algorithm functions accept two iterators that specify a range of elements. To give you a better idea of how the STL template functions work, we'll use this same approach.
Second, you must change this function into a template function.
The old version relied on the
typedef BI_StackAsVectorIterator<float> Iterator;
statement to specify the iterator's static type. If you
rewrite it as a template function, you'll be able to use
it for more than one type of container.
From the Borland C++ 4.0 IDE, reopen the STL_TEST.CPP file by
double-clicking on its name in the Project window. When the editing
window for this file appears, insert the following code directly
above the main( ) function:
template <class ForwardIterator>
void
displayMatches(ForwardIterator start,
ForwardIterator end)
{
while(start != end)
{
if((*start > 1) && (*start < 3))
{
cout << "Item " << *start;
cout << " is between 1 and 3" << endl;
}
++start;
}
}
Then, in the main( ) function, directly above the
while(!numbers.empty( )) statement, insert the following
commands:
displayMatches(numbers.begin( ), numbers.end( )); cout << endl;
Choose Save from the File menu to save these changes.
Next, choose Run from the Debug menu. After the compiler finishes
building the application, it will run the application and display
the output window. In this window, you'll see
1.01 2.02 6.06 24.24 121.2 Item 1.01 is between 1 and 3 Item 2.02 is between 1 and 3 121.2 24.24 6.06 2.02 1.01
When you've confirmed that the output is correct, double-click on the output window to close it.
Now, change the typedef statement for the Group
type to
typedef deque<float> Group;
and rebuild and run the program. The output will be the same,
which demonstrates that the displayMatches( ) template
function is compatible with the sequence containers. (By the way,
you can change the container to a list, and it will still
work.)
By now, you may be wondering why the STL is such a big deal. After all, there are several classes that the BIDS library provides that don't appear to be part of the STL.
For example, the BIDS library defines the sorted array classes TSArrayAsVector<>, TMSArrayAsVector<>, TISArrayAsVector<>, and TMISArrayAsVector<>. To implement sorting in these classes, the BIDS library uses the implementation class TMSVectorImp<>, which defines an Add( ) member function (which, in turn, inserts the elements in the correct order) and a Find( ) member function (which locates specific elements).
Instead of relying on member functions to modify the contents
of a container directly, the STL provides container classes that
define a common interface, iterator classes that modify
the class objects through that interface, and global template
functions to manipulate the containers via those iterators. If
you want to create a sorted vector of integers, you can create
a global template function similar to
template<class Container, class T >
void sorted_insert(Container c,
const T& value)
{ c.insert(lower_bound(c.begin( ), c.end( ),
value), value);
}
This function uses one of the STL's comparison functionslower_bound( )to search for the appropriate location for the value object.
If you examine the sequence classes, notice that all three of them provide the form of the insert( ) function we use here. This means that the sorted_insert( ) template function works correctly for any of these types of containers.
In contrast, to add this type of functionality to the BIDS library,
Borland created several new classes and had to modify the Add( )
member function in each class. Without question, writing and debugging
one version of a function is easier than writing and debugging
two, three, or more versions. This is how the STL can perform
complex tasks with a relatively simple framework. (For more information
on the general organization of the STL, see Standard C++ - Standard Template Library overview)
The STL is a flexible, powerful replacement for the BIDS library.
In future versions of Borland C++, you may see the TurboVision
library and ObjectWindows Library depend on STL classes and iterators
instead of their BIDS counterparts.
Copyright (c) 1996 The Cobb Group, a division of Ziff-Davis Publishing Company. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of Ziff-Davis Publishing Company is prohibited. The Cobb Group and The Cobb Group logo are trademarks of Ziff-Davis Publishing Company.